package leecode;

/**
 * @Classname
 * @Description TODO
 * @Date 2021/7/24 17:09
 * @Created by Alberthch
 * 题目：替换隐藏数字得到的最晚时间
 */
class Solution_1736 {
    // 时间复杂度O(1),空间复杂度O(1)
    public static String maximumTime(String time) {
        char[] times = time.toCharArray();
        if (times[0] == '?' && times[1] == '?') {
            times[0] = '2';
            times[1] = '3';
        }

        if (times[0] == '?' && times[1] != '?') {
            // char型数据和int型数据的判断
            // 其实char型数据可以直接进行比较
            if (times[1] <= '3') {
                times[0] = '2';
            }
            if (times[1] > '3') {
                times[0] = '1';
            }
        }

        if (times[0] != '?' && times[1] == '?') {
            if (times[0] <= '1') {
                times[1] = '9';
            }
            if (times[0] == '2') {
                times[1] = '3';
            }
        }

        if (times[3] == '?' && times[4] == '?') {
            times[3] = '5';
            times[4] = '9';
        }

        if (times[3] == '?' && times[4] != '?') {
            times[3] = '5';
        }

        if (times[3] != '?' && times[4] == '?') {
            times[4] = '9';
        }

        return new String(times);

    }

    // 方法2：贪心算法
    /**
     * 为了得到最晚有效时间，我们可以从高位向低位枚举，在保证时间有效的情况下，使得每一位尽可能取最大值。
     *
     *     因为本题中时间的位数较少，我们依次考虑每一位的规则即可。
     *
     *     第一位：若第二位的值已经确定，且值落在区间 [4,9][4,9] 中时，第一位的值最大只能为 11，否则最大可以为 22；
     *     第二位：若第一位的值已经确定，且值为 22 时，第二位的值最大为 33，否则为 99；
     *     第三位：第三位的值的选取与其它位无关，最大为 55；
     *     第四位：第四位的值的选取与其它位无关，最大为 99。
     */
    // 时间复杂度：O(1)O(1)
    //
    //空间复杂度：O(1)O(1)



    public String maximumTimeLeecode(String time) {
        char[] arr = time.toCharArray();
        if (arr[0] == '?') {
            arr[0] = ('4' <= arr[1] && arr[1] <= '9') ? '1' : '2';
        }
        if (arr[1] == '?') {
            arr[1] = (arr[0] == '2') ? '3' : '9';
        }
        if (arr[3] == '?') {
            arr[3] = '5';
        }
        if (arr[4] == '?') {
            arr[4] = '9';
        }
        return new String(arr);
    }



    public static void main(String[] args) {
        String time = "2?:?0";
        String time1 = "0?:3?";
        System.out.println(maximumTime(time));
        System.out.println(maximumTime(time1));
    }
}
